package formal.queueStack;

import java.util.HashMap;
import java.util.Stack;

/**
 * 有效的括号
 *
 * @author DengYuan2
 * @create 2021-01-28 20:43
 */
public class E_20 {
    public static void main(String[] args) {
        String s = "{[]}";
        System.out.println(isValid(s));
    }

    /**
     * 我的写法-用的substring,不太好
     * @param s
     * @return
     */
    public static boolean isValid(String s) {
        Stack<String> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            String value = s.substring(i, i + 1);
            if (isLeft(value)) {
                stack.push(value);
            } else {
                if (stack.isEmpty()) {
                    return false;
                }
                String peek = stack.peek();
                if (!isMatch(peek, value)) {
                    return false;
                } else {
                    stack.pop();
                }
            }
        }
        return stack.isEmpty();
    }

    public static boolean isLeft(String str) {
        return str.equals("(") || str.equals("[") || str.equals("{");
    }

    public static boolean isMatch(String s, String t) {
        if ((s.equals("(") && t.equals(")")) || (s.equals("[") && t.equals("]")) || (s.equals("{") && t.equals("}"))) {
            return true;
        }
        return false;
    }

    /**
     * 官方-用map来判断是否是一对匹配的括号
     * @param s
     * @return
     */
    public static boolean isValid2(String s){
        //首先从长度进行判断
        if (s.length()%2==1){
            return false;
        }
        Stack<Character> stack = new Stack<>();
        HashMap<Character, Character> map = new HashMap<>();
        map.put(']','[');
        map.put(')','(');
        map.put('}','{');

        for (char ch:s.toCharArray()){
            if (map.containsKey(ch)){
                if (stack.isEmpty() || !stack.pop().equals(map.get(ch))){
                    return false;
                }
            }else {
                stack.push(ch);
            }
        }
        return stack.isEmpty();
    }
}
